백준 1799번

오늘 풀어본 문제는 백준의 1799번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 $O$ 로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 $7$ 개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 $10$ 이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 $1$, 비숍을 놓을 수 없는 곳에는 $0$ 이 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

풀이과정

1번째 시도

문제를 보고 예전에 풀었던 N-Queen 문제와 비슷한 백트래킹 문제라는 것을 알 수 있었다. 대신 이번에는 퀸 대신 비숍을 사용하고, 놓을 수 있는 위치에 제약이 걸려있기 때문에 다음과 같은 방식을 이용하였다.

$N \times N$ 크기의 보드에는 총 $4N - 2$ 개의 대각선이 존재하고, 비숍을 두면 해당 대각선이 점유된 것으로 간주하여 백트래킹을 진행하도록 하였다.
vector<bool> 자료형 대신 unsigned long long 을 비트마스킹 하는 방식을 활용하여 비트 연산 기반의 빠른 탐색이 가능하게 하였다.
체스에서 흰색 칸과 검은 색 칸에 각각 놓인 비숍은 서로 간섭이 불가능하다는 점을 이용하여 흰색 부분과 검은 색 부분을 분리한 뒤, 각각 최대로 놓을 수 있는 비숍의 개수를 구한 뒤, 이를 합하여 최종 결과를 얻도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

int bishopCount(int N, const vector<pair<int, int>> &availablePoints, ull &lineOccupied, int start);
pair<int, int> positionToLineNum(const pair<int, int>& curr, int N);
bool check(const pair<int, int>& curr, int N, ull lineOccupied);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    vector<pair<int, int>> whitePoints;
    vector<pair<int, int>> blackPoints;

    ull lineOccupied = 0;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            int status;
            cin >> status;

            if (status == 1) {
                if ((i + j) % 2 == 0) {
                    whitePoints.emplace_back(i, j);
                }
                else {
                    blackPoints.emplace_back(i, j);
                }
            }
        }
    }

    int whiteBishopCount = bishopCount(N, whitePoints, lineOccupied, 0);
    int blackBishopCount = bishopCount(N, blackPoints, lineOccupied, 0);

    cout << whiteBishopCount + blackBishopCount;

    return 0;
}

int bishopCount(int N, const vector<pair<int, int>> &availablePoints, ull &lineOccupied, int start) {
    int maximum = 0;

    for (int curr=start; curr<availablePoints.size(); curr++) {
        if (check(availablePoints[curr], N, lineOccupied)) {
            pair<int, int> lines = positionToLineNum(availablePoints[curr], N);

            ull mask1 = 1ULL << lines.first;
            ull mask2 = 1ULL << lines.second;

            lineOccupied ^= mask1;
            lineOccupied ^= mask2;

            maximum = max(maximum, 1 + bishopCount(N, availablePoints, lineOccupied, curr + 1));

            lineOccupied ^= mask1;
            lineOccupied ^= mask2;
        }
    }

    return maximum;
}

pair<int, int> positionToLineNum(const pair<int, int>& curr, int N) {
    return make_pair(curr.first + curr.second, 3 * N - 2 + curr.first - curr.second);
}

bool check(const pair<int, int>& curr, int N, ull lineOccupied) {
    pair<int, int> lines = positionToLineNum(curr, N);

    if ((lineOccupied & (1ULL << lines.first)) || (lineOccupied & (1ULL << lines.second))) {
        return false;
    }
    else {
        return true;
    }
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

제출 자체는 한 번에 성공했지만, 실제로 답을 맞을 맞추고 시간안에 돌아가게 하는 과정에서 여러 가지 최적화 방법을 배울 수 있었다.

이 문제에 한해서이긴 하지만, 흑색 칸과 백색 칸을 분리하는 건 엄청난 아이디어였고, 비트마스킹의 강력한 성능에 대해서도 직접 체감할 수 있게 되었다. 나중에 비슷한 문제를 만나게 되면 더 잘 대처할 수 있었으면 좋겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1799

← Previous Post Next Post →